package io.github.maojian.slidingwindow;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Auther: jian.mao
 * @Date: 2022-06-23 09:55
 * @Description: https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
 */
public class Q30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int wordLength = words[0].length();
        int joinWordStrLength = wordLength * words.length;
        int sLength = s.length();
        if (sLength < joinWordStrLength) {
            return new ArrayList<>();
        }
        Map<String, Integer> wordMap = new HashMap<>();
        for (String word : words) {
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }
        Map<String, Integer> tempMap = new HashMap<>();
        for (int i = 0; i + joinWordStrLength <= sLength; i++) {
            tempMap.clear();
            String tempStr = s.substring(i, i + joinWordStrLength);
            for (int j = 0; j < joinWordStrLength; j += wordLength) {
                String curWord = tempStr.substring(j, j + wordLength);
                tempMap.put(curWord, tempMap.getOrDefault(curWord, 0) + 1);
            }
            if (tempMap.equals(wordMap)){
                list.add(i);
            }
        }

        return list;
    }

    @Test
    public void test() {
        String s = "barfoofoobarthefoobarman";
        String[] words = new String[]{"bar","foo","the"};
        findSubstring(s, words).stream().forEach(System.out::print);
    }


}
